#include<iostream>
#include<vector>
using namespace std;

void printVector(const vector<int>& v)
{
    for(auto e : v)
        cout << e << " ";
    cout << endl;
}


/*完成对数组a的指定区间[left, right]的归并排序*/
void _mergeSort(vector<int>& a, int left, int right, vector<int>& cp)
{
    if(left >= right) return;

    // 1.使左右两区间变为有序
    int mid = (left + right) / 2;
    _mergeSort(a, left, mid, cp);
    _mergeSort(a, mid+1, right, cp);

    // 2.合并两个有序数组
    int b1 = left, e1 = mid, b2 = mid+1, e2 = right;
    int i = left;
    while(b1 <= e1 && b2 <= e2)
    {
        if(a[b1] <= a[b2])
            cp[i++] = a[b1++];
        else
            cp[i++] = a[b2++];
    }
    while(b1 <= e1)
        cp[i++] = a[b1++];
    while(b2 <= e2)
        cp[i++] = a[b2++];

    // 3.拷贝回原数组
    a = cp;
}

void mergeSort(vector<int>& a)
{
    auto cp = a;
    int n = a.size();
    _mergeSort(a, 0, n-1, cp);
}

int main()
{
    vector<int> a = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8, 13, 0,-1,-4,1,33,2,2,3,3,3};
    printVector(a);
    
    mergeSort(a);
    
    printVector(a);
    
    return 0;
}